/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-23 10:57:26
 * @LastEditors: lily
 * @LastEditTime: 2021-04-27 10:38:44
 */
/*
 * @lc app=leetcode.cn id=448 lang=javascript
 *
 * [448] 找到所有数组中消失的数字
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
//  思路：哈希表
//  第一次循环记录出现的数，第二次循环[1,n]找出没出现的数
//  利用源数组减少空间复杂度

var findDisappearedNumbers = function (nums) {
    //复杂度O(n) O(1)
    let res = []
    for (const num of nums) {
        // 把num对应下标，即出现过的数，修改为相反数
        nums[Math.abs(num) - 1] = -Math.abs(nums[Math.abs(num) - 1])
    }
    // for (const [i, num] of nums.entries()) 可以这么写hhhhh
    nums.forEach((num, index) => {
        // 下标为负表示出现过，找出没出现过的数字
        if (num > 0) {
            res.push(index + 1)
        }
    });
    return res


    // 复杂度O(n) O(n)
    // let res = [], obj = {}
    // for (let num of nums) {
    //     if (!obj[num]) {
    //         obj[num] = 1
    //     }
    // }
    // for (let i = 1; i < nums.length + 1; i++) {
    //     if (!obj[i]) {
    //         res.push(i)
    //     }
    // }
    // return res

};
// @lc code=end

console.log(findDisappearedNumbers([2, 3, 4, 5, 6, 7, 8, 1]));